#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    
    public:
    int ans1(string word1, string word2){
        int len1 = word1.size(), len2 = word2.size();
        if(len1 == 0 || len2 == 0){
            return len1 + len2;
        }

        vector<vector<int>> D(len1+1, vector<int>(len2+1));
        for(int i = 0; i != len1+1; i++){
            D[i][0] = i;
        }
        for(int j = 0; j != len2+1; j++){
            D[0][j] = j;
        }

        for(int i = 1; i != len1+1; i++){
            for(int j = 1; j != len2+1; j++){
                if(word1[i-1] == word2[j-1]){
                    D[i][j] = min(min(D[i-1][j-1], D[i][j-1]+1), D[i-1][j]+1);
                }else{
                    D[i][j] = min(min(D[i-1][j-1]+1, D[i][j-1]+1), D[i-1][j]+1);
                }
            }
        }

        return D[len1][len2];
    }

};

void test1(){
    Solution s;
    string word1 = "horse", word2 = "ros";

    int ret = s.ans1(word1, word2);
    cout << ret << endl;
}

void test2(){
    Solution s;
    string word1 = "intention", word2 = "execution";

    int ret = s.ans1(word1, word2);
    cout << ret << endl;
}

void test3(){
    Solution s;
    string word1 = "zoologicoarchaeologist", word2 = "zoogeologist";

    int ret = s.ans1(word1, word2);
    cout << ret << endl;
}



int main(void){
    test1();
    test2();
    test3();

    return 0;
}